package xin.javashare.sort;

/**
 * 程序清单24.8 【堆】
 * 堆是一棵具有以下属性的二叉树，
 * 它是一棵完全二叉树，
 * 每个结点大于或等于它的的任意一个孩子；
 *
 * @param <E>
 */
public class Heap<E extends Comparable> {
    // 在堆内部，使用数组线性表表示，也可以改为其他的数据结构；
    private java.util.ArrayList<E> list = new java.util.ArrayList<E>();

    public Heap() {

    }

    public Heap(E[] objects) {
        for (int i = 0; i < objects.length; i++) {
            add(objects[i]);
        }
    }

    public void add(E newObject) {
        list.add(newObject);
        // 添加一个新的结点，首先将它添加到堆的末尾；
        int currentIndex = list.size() - 1;

        while (currentIndex > 0) {
            int parrentIndex = (currentIndex - 1) / 2;

            if (list.get(currentIndex).compareTo(list.get(parrentIndex)) > 0) {
                E temp = list.get(currentIndex);
                list.set(currentIndex, list.get(parrentIndex));
                list.set(parrentIndex, temp);
            } else
                break;

            currentIndex = parrentIndex;
        }

    }

    public E remove() {
        if (list.size() == 0) return null;
        // 删除根结点，并将堆尾部节点设为根结点；
        E removeObject = list.get(0);
        list.set(0, list.get(list.size() - 1));

        list.remove(list.size() - 1);

        int currentIndex = 0;
        while (currentIndex < list.size()) {
            int leftChildIndex = 2 * currentIndex + 1;
            int rightChildIndex = 2 * currentIndex + 2;

            if (leftChildIndex >= list.size()) break;
            int maxIndex = leftChildIndex;
            if (rightChildIndex < list.size()) {
                if (list.get(maxIndex).compareTo(list.get(rightChildIndex)) < 0) {
                    maxIndex = rightChildIndex;
                }
            }

            if (list.get(currentIndex).compareTo(list.get(maxIndex)) < 0) {
                E temp = list.get(maxIndex);
                list.set(maxIndex, list.get(currentIndex));
                list.set(currentIndex, temp);
                currentIndex = maxIndex;
            } else
                break;
        }

        return removeObject;
    }

    public int getSize() {
        return list.size();
    }
}
